{"id":{"repo_id":"bu","oai_identifier":"oai:open.bu.edu:2144/53768"},"canonical_url":"https://search.ndltd.org/etd/bu/oai:open.bu.edu:2144/53768","repository":{"repo_id":"bu","name":"Boston University","base_url":"https://open.bu.edu/oai/request"},"display":{"title":"Unconstrained online convex optimization: regularization in the adversarial setting and beyond","abstract":"Most first-order optimizers require a learning rate that depends on the problem scale, the distance from initialization to an optimal solution, and receive gradient feedback that is stochastic, corrupted, or both. This thesis studies whether these two difficulties can be resolved simultaneously: we develop online convex optimization algorithms on an unconstrained domain that adapt to the unknown problem scale while operating under inexact gradient feedback. We consider two models of gradient inexactness: a stochastic model, where each gradient is perturbed by zero-mean heavy-tailed noise with bounded p-th moment for p in (1,2], and an adversarial model, where up to k gradient observations are arbitrarily corrupted. In both settings, the algorithm observes only the corrupted gradient yet must control regret against the true gradients. The central technique combines gradient clipping with a time-varying regularizer: clipping limits the influence of extreme observations, while the regularizer cancels the resulting clipping bias and controls iterate growth. The latter is a genuine obstacle in unconstrained online convex optimization, where iterates can grow exponentially fast. Under heavy-tailed gradient noise, we establish the first high-probability comparator-adaptive regret bound Õ(‖x‖ T^(1/p)) for any comparator x in the unconstrained setting, matching existing lower bounds. Under adversarial corruption, we provide an algorithm achieving Õ(‖x‖(√T + k)) regret with a matching lower bound. We then resolve a puzzle from practice: explicit regularization is never implemented in stochastic convex optimization, yet clipping alone works well. Our explanation is structural: the environment a learner faces under stochastic convex optimization is cooperative in that every feedback carries information about learning a fixed objective, whereas general online convex optimization is adversarial. We formalize this as the stochastic-like condition, under which iterate stability follows: the iterates of any comparator-adaptive algorithm automatically remain near the optimum without explicit regularization. This yields a black-box reduction: any comparator-adaptive online learner inherits high-probability convergence guarantees in stochastic convex optimization. As a further application of iterate stability, we obtain comparator-adaptive algorithms for stochastic fixed point iterations, resolving the stochastic setting left open in prior work.","abstract_html":"Most first-order optimizers require a learning rate that depends on the problem scale, the distance from initialization to an optimal solution, and receive gradient feedback that is stochastic, corrupted, or both. This thesis studies whether these two difficulties can be resolved simultaneously: we develop online convex optimization algorithms on an unconstrained domain that adapt to the unknown problem scale while operating under inexact gradient feedback. We consider two models of gradient inexactness: a stochastic model, where each gradient is perturbed by zero-mean heavy-tailed noise with bounded p-th moment for p in (1,2], and an adversarial model, where up to k gradient observations are arbitrarily corrupted. In both settings, the algorithm observes only the corrupted gradient yet must control regret against the true gradients. The central technique combines gradient clipping with a time-varying regularizer: clipping limits the influence of extreme observations, while the regularizer cancels the resulting clipping bias and controls iterate growth. The latter is a genuine obstacle in unconstrained online convex optimization, where iterates can grow exponentially fast. Under heavy-tailed gradient noise, we establish the first high-probability comparator-adaptive regret bound Õ(‖x‖ T^(1/p)) for any comparator x in the unconstrained setting, matching existing lower bounds. Under adversarial corruption, we provide an algorithm achieving Õ(‖x‖(√T + k)) regret with a matching lower bound. We then resolve a puzzle from practice: explicit regularization is never implemented in stochastic convex optimization, yet clipping alone works well. Our explanation is structural: the environment a learner faces under stochastic convex optimization is cooperative in that every feedback carries information about learning a fixed objective, whereas general online convex optimization is adversarial. We formalize this as the stochastic-like condition, under which iterate stability follows: the iterates of any comparator-adaptive algorithm automatically remain near the optimum without explicit regularization. This yields a black-box reduction: any comparator-adaptive online learner inherits high-probability convergence guarantees in stochastic convex optimization. As a further application of iterate stability, we obtain comparator-adaptive algorithms for stochastic fixed point iterations, resolving the stochastic setting left open in prior work.","abstract_has_math":false,"creators":["Zhang, Jiujia"],"institution":"Boston University","degree_name":"Doctor of Philosophy","degree_level":"doctoral","degree_discipline":"Electrical & Computer Engineering","degree_department":null,"school":null,"contributors":[],"advisors":["Cutkosky, Ashok"],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-11-18T20:30:44Z","subjects":["Artificial intelligence","Applied mathematics","Computer science","Gradient clipping","Online convex optimization","Parameter-free online learning","Regret analysis","Regularization","Stochastic convex optimization"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[{"key":"dc:identifier.orcid","label":"ORCID","values":["0000-0002-8940-8656"],"render_values":[{"text":"0000-0002-8940-8656","href":"https://orcid.org/0000-0002-8940-8656","code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/2144/53768","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/2144/53768","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://open.bu.edu/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aopen.bu.edu%3A2144%2F53768","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Cutkosky, Ashok"]},{"key":"dc:creator","label":"Author","values":["Zhang, Jiujia"]},{"key":"dc:identifier.orcid","label":"ORCID","values":["0000-0002-8940-8656"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2026-10-22T17:54:45Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2026-10-22T17:54:45Z"]},{"key":"dc:date.issued","label":"Date","values":["2026"]},{"key":"dc:date.updated","label":"Dc Date Updated","values":["2026-10-20T16:15:15Z"]},{"key":"dc:type","label":"Dc Type","values":["Thesis/Dissertation"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Boston University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Artificial intelligence","Applied mathematics","Computer science","Gradient clipping","Online convex optimization","Parameter-free online learning","Regret analysis","Regularization","Stochastic convex optimization"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/2144/53768"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["2026"]},{"key":"dc:description.abstract","label":"Abstract","values":["Most first-order optimizers require a learning rate that depends on the problem scale, the distance from initialization to an optimal solution, and receive gradient feedback that is stochastic, corrupted, or both. This thesis studies whether these two difficulties can be resolved simultaneously: we develop online convex optimization algorithms on an unconstrained domain that adapt to the unknown problem scale while operating under inexact gradient feedback. We consider two models of gradient inexactness: a stochastic model, where each gradient is perturbed by zero-mean heavy-tailed noise with bounded p-th moment for p in (1,2], and an adversarial model, where up to k gradient observations are arbitrarily corrupted. In both settings, the algorithm observes only the corrupted gradient yet must control regret against the true gradients. The central technique combines gradient clipping with a time-varying regularizer: clipping limits the influence of extreme observations, while the regularizer cancels the resulting clipping bias and controls iterate growth. The latter is a genuine obstacle in unconstrained online convex optimization, where iterates can grow exponentially fast. Under heavy-tailed gradient noise, we establish the first high-probability comparator-adaptive regret bound Õ(‖x‖ T^(1/p)) for any comparator x in the unconstrained setting, matching existing lower bounds. Under adversarial corruption, we provide an algorithm achieving Õ(‖x‖(√T + k)) regret with a matching lower bound. We then resolve a puzzle from practice: explicit regularization is never implemented in stochastic convex optimization, yet clipping alone works well. Our explanation is structural: the environment a learner faces under stochastic convex optimization is cooperative in that every feedback carries information about learning a fixed objective, whereas general online convex optimization is adversarial. We formalize this as the stochastic-like condition, under which iterate stability follows: the iterates of any comparator-adaptive algorithm automatically remain near the optimum without explicit regularization. This yields a black-box reduction: any comparator-adaptive online learner inherits high-probability convergence guarantees in stochastic convex optimization. As a further application of iterate stability, we obtain comparator-adaptive algorithms for stochastic fixed point iterations, resolving the stochastic setting left open in prior work."]},{"key":"dc:title","label":"Title","values":["Unconstrained online convex optimization: regularization in the adversarial setting and beyond"]}]}],"canonical_facts":{"dc:contributor.advisor":["Cutkosky, Ashok"],"dc:creator":["Zhang, Jiujia"],"dc:date.accessioned":["2026-10-22T17:54:45Z"],"dc:date.available":["2026-10-22T17:54:45Z"],"dc:date.issued":["2026"],"dc:date.updated":["2026-10-20T16:15:15Z"],"dc:description":["2026"],"dc:description.abstract":["Most first-order optimizers require a learning rate that depends on the problem scale, the distance from initialization to an optimal solution, and receive gradient feedback that is stochastic, corrupted, or both. This thesis studies whether these two difficulties can be resolved simultaneously: we develop online convex optimization algorithms on an unconstrained domain that adapt to the unknown problem scale while operating under inexact gradient feedback. We consider two models of gradient inexactness: a stochastic model, where each gradient is perturbed by zero-mean heavy-tailed noise with bounded p-th moment for p in (1,2], and an adversarial model, where up to k gradient observations are arbitrarily corrupted. In both settings, the algorithm observes only the corrupted gradient yet must control regret against the true gradients. The central technique combines gradient clipping with a time-varying regularizer: clipping limits the influence of extreme observations, while the regularizer cancels the resulting clipping bias and controls iterate growth. The latter is a genuine obstacle in unconstrained online convex optimization, where iterates can grow exponentially fast. Under heavy-tailed gradient noise, we establish the first high-probability comparator-adaptive regret bound Õ(‖x‖ T^(1/p)) for any comparator x in the unconstrained setting, matching existing lower bounds. Under adversarial corruption, we provide an algorithm achieving Õ(‖x‖(√T + k)) regret with a matching lower bound. We then resolve a puzzle from practice: explicit regularization is never implemented in stochastic convex optimization, yet clipping alone works well. Our explanation is structural: the environment a learner faces under stochastic convex optimization is cooperative in that every feedback carries information about learning a fixed objective, whereas general online convex optimization is adversarial. We formalize this as the stochastic-like condition, under which iterate stability follows: the iterates of any comparator-adaptive algorithm automatically remain near the optimum without explicit regularization. This yields a black-box reduction: any comparator-adaptive online learner inherits high-probability convergence guarantees in stochastic convex optimization. As a further application of iterate stability, we obtain comparator-adaptive algorithms for stochastic fixed point iterations, resolving the stochastic setting left open in prior work."],"dc:identifier.orcid":["0000-0002-8940-8656"],"dc:identifier.uri":["https://hdl.handle.net/2144/53768"],"dc:language.iso":["en_US"],"dc:subject":["Artificial intelligence","Applied mathematics","Computer science","Gradient clipping","Online convex optimization","Parameter-free online learning","Regret analysis","Regularization","Stochastic convex optimization"],"dc:title":["Unconstrained online convex optimization: regularization in the adversarial setting and beyond"],"dc:type":["Thesis/Dissertation"],"thesis:degree_discipline":["Electrical & Computer Engineering"],"thesis:degree_level":["doctoral"],"thesis:degree_name":["Doctor of Philosophy"],"thesis:institution_name":["Boston University"]},"updated_at":"2026-11-18T20:30:44Z"}