- StreaMRAK - потоковый адаптивный алгоритм ядра с несколькими разрешениями (arXiv)
Автор : : Андреас Осландсботн, Желько Керета, Валерия Наумова, Йоав Фройнд, Александр Клонингер
Аннотация: Регрессия гребня ядра (KRR) — популярная схема нелинейного непараметрического обучения. Однако существующие реализации KRR требуют, чтобы все данные хранились в основной памяти, что серьезно ограничивает использование KRR в контекстах, где размер данных намного превышает размер памяти. Такие приложения становятся все более распространенными в интеллектуальном анализе данных, биоинформатике и управлении. Мощной парадигмой вычислений с наборами данных, которые слишком велики для памяти, является потоковая модель вычислений, в которой мы обрабатываем одну выборку данных за раз, отбрасывая каждую выборку перед переходом к следующей. В этой статье мы предлагаем StreaMRAK — потоковую версию KRR. StreaMRAK совершенствует существующие схемы KRR, разделяя проблему на несколько уровней разрешения, что позволяет постоянно совершенствовать прогнозы. Алгоритм снижает требования к памяти за счет непрерывной и эффективной интеграции новых образцов в обучающую модель. Благодаря новой схеме субдискретизации StreaMRAK сокращает объем памяти и вычислительные сложности, создавая эскиз исходных данных, в котором плотность субдискретизации адаптируется к пропускной способности ядра и локальной размерности данных. Мы представляем наглядное исследование двух синтетических задач и прогнозирования траектории двойного маятника. Результаты показывают, что предложенный алгоритм является быстрым и точным.
2. Гиперсжатие матриц, потоковые алгоритмы и НРС: случай большого алфавита (arXiv)
Автор: Шринивасан Аруначалам, Жоао Ф. Доригуэльо
Аннотация: Мы доказываем гиперсжимающее неравенство для матриц-функций, определенных в больших алфавитах, обобщая результат Бен-Аройи, Регева, де Вольфа (FOCS’08) для булевого алфавита. Для таких случаев мы доказываем обобщение 2-равномерного неравенства выпуклости Болла, Карлена, Либа (Inventiones Mathematicae'94). Используя наше неравенство, мы представляем верхнюю и нижнюю оценки сложности связи скрытого гиперсопоставления, когда оно определено для больших алфавитов, что обобщает хорошо известную булеву проблему скрытого сопоставления. Затем мы рассматриваем потоковые алгоритмы для аппроксимации ценности уникальных игр на гиперграфе t-гиперребер: аргумент подсчета ребер дает r-аппроксимацию с пространством O(logn). С другой стороны, с помощью нашей нижней границы связи мы показываем, что каждый потоковый алгоритм в состязательной модели, достигающий (r−ε)-аппроксимации, требует квантового пространства Ω(n1−2/t). Это обобщает плодотворную работу Капралова, Ханны, Судана (SODA'15) и расширяет результаты квантовой настройки Капралова, Крачуна (STOC'19) и Чоу и др. (СТОК’22). Далее мы приведем нижнюю оценку для локально декодируемых кодов (LDC) в больших алфавитах. LDC C:Znr→ZNr — это кодирование x в кодовое слово таким образом, что можно восстановить произвольное xi (с вероятностью не менее 1/r+ε), выполнив несколько запросов к поврежденному кодовому слову. Главный вопрос здесь — компромисс между N и n. С помощью гиперсжатия мы даем экспоненциальную нижнюю оценку N=2Ω(ε4n/r4) для 2-запросных (возможно, нелинейных) НРС над Zr и, используя некоммутативное неравенство Хинчина, мы улучшили нашу оценку до N=2Ω(ε2n/r2 ). Ранее были известны экспоненциальные нижние границы для r=2 (Керенидис, де Вольф (JCSS’04)) и линейных кодов (Двир, Шпилька (SICOMP’07))
